n = 4

#右下左上
directions={0:[0,1],1:[1,0],2:[0,-1],3:[-1,0]}
def dfs(ans,n,i,j,ac,rank):
    #递归出口
    if ac>n*n:
        return None
    ans[i][j]=ac
    for k in range(4):
        x,y=i+directions[(rank+k)%4][0],j+directions[(rank+k)%4][1]
        if x>=0 and x<n and y>=0 and y<n and ans[x][y]==0:
            dfs(ans,n,x,y,ac+1,(rank+k)%4)
def generateMatrix(n):
    ans=[[0 for _ in range(n)] for _ in range(n)]
    dfs(ans,n,0,0,1,0)
    return ans
print(generateMatrix(n))